package cn.algorithms_4ed.base.demo;

import cn.stdlib.In;
import cn.stdlib.StdOut;

/**
 * #请替换掉这里的东东#
 * <p/>
 * User: erhu
 * Date: 13-6-12
 * Time: 上午10:39
 */
public class ThreeSum {

    public static int count(int[] a) {
        int length = a.length;
        int cnt = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                for (int k = j + 1; k < length; k++) {
                    if (a[i] + a[j] + a[k] == 0) {
                        cnt++;
                    }
                }
            }

        }
        return cnt;
    }

    public static void main(String[] args) {
        String file_1K = "/Users/erhu/Dropbox/workspace/java-study/algs4-data/1Kints.txt";
        String file_2K = "/Users/erhu/Dropbox/workspace/java-study/algs4-data/2Kints.txt";
        String file_4K = "/Users/erhu/Dropbox/workspace/java-study/algs4-data/4Kints.txt";
        String file_8K = "/Users/erhu/Dropbox/workspace/java-study/algs4-data/8Kints.txt";
        long begin = System.currentTimeMillis();
        int[] a = new In(file_1K).readAllInts();
        StdOut.println("1K => " + count(a) + " => " + (System.currentTimeMillis() - begin));

        begin = System.currentTimeMillis();
        int[] ab = new In(file_2K).readAllInts();
        StdOut.println("2K => " + count(ab) + " => " + (System.currentTimeMillis() - begin));

        begin = System.currentTimeMillis();
        int[] ac = new In(file_4K).readAllInts();
        StdOut.println("4K => " + count(ac) + " => " + (System.currentTimeMillis() - begin));
        /*
           1K => 70 => 482
           2K => 528 => 3133
           4K => 4039 => 5275
        */
/*
        begin = System.currentTimeMillis();
        int[] ad = new In(file_8K).readAllInts();
        StdOut.println("8K => " + count(ad) + " => " + (System.currentTimeMillis() - begin));
*/
    }

}
